package leetcode.weekly.week334;

import java.util.PriorityQueue;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	public int minimumTime(int[][] grid) {
		if (grid[0][1] > 1 && grid[1][0] > 1) {
			return -1;
		}
		int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
		int m = grid.length, n = grid[0].length;
		Integer[][] been = new Integer[m][n];
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 时间，x,y
		queue.add(new int[] { 0, 0, 0 });
		been[0][0] = 0;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int t = cur[0], x = cur[1], y = cur[2];
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && been[nextx][nexty] == null) {
					long nextt =grid[nextx][nexty]>= t?  1l * ((grid[nextx][nexty] - t) / 2) * 2 + t + 1 : t + 1;
					been[nextx][nexty] = (int) nextt;
					if (nextx == m - 1 && nexty == n - 1) {
						return (int) nextt;
					}
					queue.add(new int[] { (int) nextt, nextx, nexty });
				}
			}
		}
		return -1;
	}

}
